package cn.edu.xjtu.carlWay.tree.symmetricTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 101. 对称二叉树
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称
 * <p>
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
public class Solution {
    /**
     * 递归法
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return symmetric(root.left, root.right);
    }

    public boolean symmetric(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return symmetric(node1.left, node2.right) && symmetric(node1.right, node2.left);
    }

    /**
     * 迭代法
     *
     * @param root
     * @return
     */
    public boolean isSymmetric1(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> dequeLeft = new LinkedList<>();
        Deque<TreeNode> dequeRight = new LinkedList<>();
        dequeLeft.addLast(root.left);
        dequeRight.addLast(root.right);
        while (!dequeLeft.isEmpty()) {
            TreeNode leftNode = dequeLeft.removeFirst();
            TreeNode rightNode = dequeRight.removeFirst();
            if (!judgeEqual(leftNode, rightNode)) {
                return false;
            }
            // 这里其实可以只写一个不为null就行，因为如果一个为null一个不为null在上面的函数直接就return false结束了
            if (leftNode != null && rightNode != null) {
                dequeLeft.addLast(leftNode.left);
                dequeLeft.addLast(leftNode.right);

                dequeRight.addLast(rightNode.right);
                dequeRight.addLast(rightNode.left);
            }
        }
        return true;
    }

    public boolean judgeEqual(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.val != node2.val) {
            return false;
        }
        return true;
    }
}
